package com.jack.leetcode.每日一题;

public class 每个元音包含偶数次的最长子字符串 {

    public static void main(String[] args) {
        String s = "eleetminicoworoep";
        System.out.println(findTheLongestSubstring(s));
        s = "leetcodeisgreat";
        System.out.println(findTheLongestSubstring(s));
    }

    public static int findTheLongestSubstring(String s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }
        int[][] pre = new int[n][5];
        int start = getIndex(s.charAt(0));
        if (start != -1) {
            pre[0][start]++;
        }
        for (int i = 1; i < n; i++) {
            int cur = getIndex(s.charAt(i));
            for (int j = 0; j < 5; j++) {
                if (cur == j) {
                    pre[i][j] = pre[i - 1][j] + 1;
                } else {
                    pre[i][j] = pre[i - 1][j];
                }
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < n - i; j++) {
                if (valid(pre, s, j, i + j)) {
                    return i + 1;
                }
            }
        }
        return 0;
    }

    private static boolean valid(int[][] pre, String s, int i, int j) {
        int idx = getIndex(s.charAt(i));
        for (int k = 0; k < 5; k++) {
            if (((pre[j][k] - pre[i][k] + (idx == k ? 1 : 0)) & 1) == 1) {
                return false;
            }
        }
        return true;
    }

    public static int getIndex(char ch) {
        switch (ch) {
            case 'a':
                return 0;
            case 'e':
                return 1;
            case 'i':
                return 2;
            case 'o':
                return 3;
            case 'u':
                return 4;
        }
        return -1;
    }
}